package leetcode.code1210;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.H;

import leetcode.IDebug;

public class Solution implements IDebug {

	int n;
	int[][] grid;
	boolean[][][] status;

	public int minimumMoves(int[][] grid) {
		n = grid.length;
		this.grid = grid;
		Queue<int[]> queue = new LinkedList<>();
		status = new boolean[n][n][2];
		status[0][1][0] = true;
		queue.add(new int[] { 0, 1, 0 });
		int ans = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				int[] cur = queue.poll();
				int x = cur[0], y = cur[1];
				if (x == n - 1 && y == n - 1 && cur[2] == 0) {
					return ans;
				}
				if (cur[2] == 0) {
					int tx = x, ty = y - 1;
					if (down(x, y, tx, ty)) {
						add(queue, x + 1, y, 0);
						add(queue, x + 1, y - 1, 1);
					}
					if (f(y + 1) && grid[x][y + 1] == 0) {
						add(queue, x, y + 1, 0);
					}
				} else {
					int tx = x - 1, ty = y;
					if (right(x, y, tx, ty)) {
						add(queue, x - 1, y + 1, 0);
						add(queue, x, y + 1, 1);
					}
					if (f(x + 1) && grid[x + 1][y] == 0) {
						add(queue, x + 1, y, 1);
					}
				}
				size--;
			}
			ans++;
		}
		return -1;
	}

	private void add(Queue<int[]> queue, int x, int y, int z) {
		if (!status[x][y][z]) {
			status[x][y][z] = true;
			queue.add(new int[] { x, y, z });
		}
	}

	private boolean right(int x, int y, int tx, int ty) {
		return check(x, y + 1, tx, ty + 1);
	}

	private boolean down(int x, int y, int tx, int ty) {
		return check(x + 1, y, tx + 1, ty);
	}

	private boolean check(int x, int y, int tx, int ty) {
		return f(x) && f(y) && f(tx) && f(ty) && ff(x, y) && ff(tx, ty);
	}

	private boolean ff(int x, int y) {
		return this.grid[x][y] == 0;
	}

	private boolean f(int i) {
		return i >= 0 && i < n;
	}

	@Override
	public void debug4() {
		H.compare(-1, this.minimumMoves(H.str2array1(
				"[[0,0,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,1,0,1],[1,0,0,1,0,0,1,0,1,0],[0,0,0,1,0,1,0,1,0,0],[0,0,0,0,1,0,0,0,0,1],[0,0,1,0,0,0,0,0,0,0],[1,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,0]]")));
//		H.compare(11, this.minimumMoves(H.str2array1("[[0,0,0,0,0,1],[1,1,0,0,1,0],[0,0,0,0,1,1],[0,0,1,0,1,0],[0,1,1,0,0,0],[0,1,1,0,0,0]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
